home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / CPP / HUGEAR.ZIP / HVECTIMP.H < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-27  |  39.2 KB  |  1,309 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  HVECTIMP.H                                                            */
  4. /*                                                                        */
  5. /*------------------------------------------------------------------------*/
  6.  
  7. #if !defined( HVECTIMP_H )
  8. #define HVECTIMP_H
  9.  
  10. #if defined(__DPMI32__) || defined(__WIN32__)
  11. #error Can not use huge vectors in a 32 bit model
  12. #endif
  13.  
  14. #include <iostream.h>
  15.  
  16. #if !defined( __LIMITS_H )
  17. #include <limits.h>
  18. #endif  // __LIMITS_H
  19.  
  20. #if !defined( __CHECKS_H )
  21. #include <checks.h>
  22. #endif  // __CHECKS_H
  23.  
  24. #if !defined( __CLASSLIB_DEFS_H )
  25. #include "classlib\defs.h"
  26. #endif  // __CLASSLIB_DEFS_H
  27.  
  28. #if !defined( __CLASSLIB_STDTEMPL_H )
  29. #include "classlib\stdtempl.h"
  30. #endif  // __CLASSLIB_STDTEMPL_H
  31.  
  32. #if !defined( HALLOCTR_H )
  33. #include "halloctr.h"
  34. #endif  // HALLOCTR_H
  35.  
  36. #if !defined( __CLASSLIB_MEMMGR_H )
  37. #include "classlib\memmgr.h"
  38. #endif  // __CLASSLIB_MEMMGR_H
  39.  
  40. #if !defined( __CLASSLIB_VOIDP_H )
  41. #include "classlib\voidp.h"
  42. #endif  // __CLASSLIB_VOIDP_H
  43.  
  44. #pragma option -Vo-
  45. #if defined( BI_CLASSLIB_NO_po )
  46. #pragma option -po-
  47. #endif
  48.  
  49. /*------------------------------------------------------------------------*/
  50. /*                                                                        */
  51. /*  template <class T, class Alloc> class THugeVectorImpBase              */
  52. /*                                                                        */
  53. /*  Implements the base functionality for a managed vector of objects of  */
  54. /*  type T.  Assumes that T has meaningful copy semantics and a default   */
  55. /*  constructor.                                                          */
  56. /*                                                                        */
  57. /*------------------------------------------------------------------------*/
  58.  
  59. template <class T, class Alloc> class THugeVectorImpBase :
  60.     public Alloc
  61. {
  62.  
  63. public:
  64.  
  65.     THugeVectorImpBase() : Data(0), Lim(0) {}
  66.  
  67.     THugeVectorImpBase( unsigned long sz, unsigned long d ) :
  68.         Data( (T __huge *)(farmalloc(sizeof(T) * sz)) ),
  69.         Lim(sz)
  70.         {
  71.         }
  72.  
  73.     THugeVectorImpBase( const THugeVectorImpBase<T,Alloc>& );
  74.  
  75.     const THugeVectorImpBase<T,Alloc>& operator = (
  76.                 const THugeVectorImpBase<T,Alloc>& );
  77.  
  78.     ~THugeVectorImpBase()
  79.         {
  80.         farfree (Data);
  81.         }
  82.  
  83.     unsigned long Limit() const
  84.         {
  85.         return Lim;
  86.         }
  87.  
  88.     virtual unsigned long Top() const
  89.         {
  90.         return Lim;
  91.         }
  92.  
  93.     virtual unsigned long Count() const
  94.         {
  95.         return Lim;
  96.         }
  97.  
  98.     int Resize( unsigned long, unsigned long = 0 );
  99.  
  100.     virtual unsigned long GetDelta() const
  101.         {
  102.         return 0;
  103.         }
  104.  
  105. protected:
  106.  
  107.     T __huge * Data;
  108.     unsigned long Lim;
  109.  
  110.     virtual void Zero( unsigned long, unsigned long)
  111.         {
  112.         }
  113.  
  114. };
  115.  
  116. template <class T, class Alloc>
  117. THugeVectorImpBase<T,Alloc>::THugeVectorImpBase(
  118.         const THugeVectorImpBase<T,Alloc>& v ) :
  119.     Data( (T __huge *)(farmalloc(sizeof(T) * v.Lim)) ),
  120.     Lim(v.Lim)
  121. {
  122.     PRECONDITION( Lim == 0 || (Data != 0 && v.Data != 0) );
  123.     for( unsigned long i = 0; i < Lim; i++ )
  124.         Data[i] = v.Data[i];
  125. }
  126.  
  127. template <class T, class Alloc>
  128. const THugeVectorImpBase<T,Alloc>& THugeVectorImpBase<T,Alloc>::operator = ( const THugeVectorImpBase<T,Alloc>& v )
  129. {
  130.     if( Data != v.Data )
  131.         {
  132.         farfree (Data);
  133.         Data = (T __huge *)(farmalloc(sizeof(T) * v.Lim));
  134.         CHECK( Data != 0 );
  135.         Lim = v.Lim;
  136.         for( unsigned long i = 0; i < Lim; i++ )
  137.             Data[i] = v.Data[i];
  138.         }
  139.     return *this;
  140. }
  141.  
  142. inline unsigned long NextDelta( unsigned long sz, unsigned long delta )
  143. {
  144.     return (sz%delta) ? ((sz+delta)/delta)*delta : sz;
  145. }
  146.  
  147. template <class T, class Alloc>
  148. int THugeVectorImpBase<T,Alloc>::Resize( unsigned long newSz, unsigned long offset )
  149. {
  150.     if( newSz <= Lim || GetDelta() == 0 )
  151.         return 0;
  152.     unsigned long sz = Lim + NextDelta( newSz - Lim, GetDelta() );
  153.     T __huge * temp = (T __huge *)(farmalloc(sizeof(T) * sz));
  154.     unsigned long last = min( sz-offset, Lim );
  155.     for( unsigned long i = 0; i < last; i++ )
  156.         temp[i+offset] = Data[i];
  157.     farfree ( Data );
  158.     Data = temp;
  159.     Lim = sz;
  160.     Zero( last+offset, sz );
  161.     return 1;
  162. }
  163.  
  164. /*------------------------------------------------------------------------*/
  165. /*                                                                        */
  166. /*  template <class T, class Alloc> class TMHugeVectorImp                 */
  167. /*                                                                        */
  168. /*  Implements a managed vector of objects of type T.  Assumes that       */
  169. /*  T has meaningful copy semantics and a default constructor.            */
  170. /*                                                                        */
  171. /*------------------------------------------------------------------------*/
  172.  
  173. template <class T,class Alloc> class TMHugeVectorIteratorImp;
  174.  
  175. template <class T,class Alloc> class TMHugeVectorImp :
  176.     public THugeVectorImpBase<T,Alloc>
  177. {
  178.  
  179. public:
  180.  
  181.     typedef void (*IterFunc)(T __huge &, void *);
  182.     typedef int  (*CondFunc)(const T __huge &, void *);
  183.  
  184.     friend TMHugeVectorIteratorImp<T,Alloc>;
  185.  
  186.     TMHugeVectorImp() : THugeVectorImpBase<T,Alloc>() {}
  187.     TMHugeVectorImp( unsigned long sz, unsigned long d = 0 ) : THugeVectorImpBase<T,Alloc>(sz,d) {}
  188.  
  189.     T __huge & operator [] ( unsigned long index )
  190.         {
  191.         PRECONDITION( Lim == 0 || Data != 0 && index < Lim );
  192.         return Data[index];
  193.         }
  194.  
  195.    T __huge & operator [] ( unsigned long index ) const
  196.         {
  197.         PRECONDITION( Lim > 0 && Data != 0 && index < Lim );
  198.         return Data[index];
  199.         }
  200.  
  201.     void Flush( unsigned long = ULONG_MAX, unsigned long = 0 ) {}
  202.  
  203.     void ForEach( IterFunc iter, void *args )
  204.         {
  205.         ForEach( iter, args, 0, Count() );
  206.         }
  207.  
  208.     void ForEach( IterFunc iter, void *args,
  209.                   unsigned long start, unsigned long stop );
  210.  
  211.     T __huge *FirstThat( CondFunc cond, void *args,
  212.                            unsigned long start, unsigned long stop) const;
  213.  
  214.     T __huge *FirstThat( CondFunc cond, void *args ) const
  215.         {
  216.         return FirstThat( cond, args, 0, Count() );
  217.         }
  218.  
  219.     T __huge *LastThat( CondFunc cond, void *args,
  220.                           unsigned long start, unsigned long stop ) const;
  221.  
  222.     T __huge *LastThat( CondFunc cond, void *args ) const
  223.         {
  224.         return LastThat( cond, args, 0, Count() );
  225.         }
  226.  
  227. };
  228.  
  229. template <class T, class Alloc>
  230. void TMHugeVectorImp<T,Alloc>::ForEach( IterFunc iter, void *args,
  231.                                     unsigned long start, unsigned long stop )
  232. {
  233.     for( unsigned long cur = start; cur < stop; cur++ )
  234.         iter( Data[cur], args );
  235. }
  236.  
  237. template <class T, class Alloc>
  238. T __huge *TMHugeVectorImp<T,Alloc>::FirstThat( CondFunc cond, void *args,
  239.                                     unsigned long start, unsigned long stop ) const
  240. {
  241.     for( unsigned long cur = start; cur < stop; cur++ )
  242.         if( cond( Data[cur], args ) != 0 )
  243.             return &(T __huge &)Data[cur];
  244.     return 0;
  245. }
  246.  
  247. template <class T, class Alloc>
  248. T __huge *TMHugeVectorImp<T,Alloc>::LastThat( CondFunc cond, void *args,
  249.                                    unsigned long start, unsigned long stop ) const
  250. {
  251.     T __huge *res = 0;
  252.     for( unsigned long cur = start; cur < stop; cur++ )
  253.         if( cond( Data[cur], args ) != 0 )
  254.             res = &(T __huge &)Data[cur];
  255.     return res;
  256. }
  257.  
  258. /*------------------------------------------------------------------------*/
  259. /*                                                                        */
  260. /*  template <class T, class Alloc> class TMHugeVectorIteratorImp         */
  261. /*                                                                        */
  262. /*  Implements a vector iterator.  This iterator works with any direct,   */
  263. /*  managed vector.  For indirect vectors, see TMIHugeVectorIteratorImp.  */
  264. /*                                                                        */
  265. /*------------------------------------------------------------------------*/
  266.  
  267. template <class T, class Alloc> class TMHugeVectorIteratorImp
  268. {
  269.  
  270. public:
  271.  
  272.     TMHugeVectorIteratorImp( const TMHugeVectorImp<T,Alloc>&v )
  273.         {
  274.         Vect = &v;
  275.         Restart(0,v.Top());
  276.         }
  277.  
  278.     TMHugeVectorIteratorImp( const TMHugeVectorImp<T,Alloc>&v,
  279.                          unsigned long start,
  280.                          unsigned long stop
  281.                          )
  282.         {
  283.         Vect = &v;
  284.         Restart( start, stop );
  285.         }
  286.  
  287.     operator int() const
  288.         {
  289.         return Cur < Upper;
  290.         }
  291.  
  292.     const T __huge & Current() const
  293.         {
  294.         PRECONDITION( Cur < Upper );
  295.         return (*Vect)[Cur];
  296.         }
  297.  
  298.     const T __huge & operator ++ ( int )
  299.         {
  300.         const T __huge & temp = Current();
  301.         Cur++;
  302.         return temp;
  303.         }
  304.  
  305.     const T __huge & operator ++ ()
  306.         {
  307.         PRECONDITION( Cur < Upper );
  308.         Cur++;
  309.         return Current();
  310.         }
  311.  
  312.     void Restart()
  313.         {
  314.         Restart(Lower,Upper);
  315.         }
  316.  
  317.     void Restart( unsigned long start, unsigned long stop )
  318.         {
  319.         Cur = Lower = start;
  320.         Upper = stop;
  321.         }
  322.  
  323. private:
  324.  
  325.     const TMHugeVectorImp<T,Alloc> *Vect;
  326.     unsigned long Cur;
  327.     unsigned long Lower, Upper;
  328.  
  329. };
  330.  
  331. /*------------------------------------------------------------------------*/
  332. /*                                                                        */
  333. /*  template <class T> class THugeVectorImp                               */
  334. /*  template <class T> class THugeVectorIteratorImp                       */
  335. /*                                                                        */
  336. /*  Implements a vector of objects of type T using THugeStandardAllocator */
  337. /*  as its memory manager. Assumes that T has meaningful copy semantics   */
  338. /*  and a default constructor.                                            */
  339. /*                                                                        */
  340. /*------------------------------------------------------------------------*/
  341.  
  342. template <class T> class THugeVectorImp :
  343.     public TMHugeVectorImp<T,THugeStandardAllocator>
  344. {
  345.  
  346. public:
  347.  
  348.     THugeVectorImp()
  349.         {
  350.         }
  351.  
  352.     THugeVectorImp( unsigned long sz, unsigned long = 0 ) :
  353.         TMHugeVectorImp<T,THugeStandardAllocator>( sz )
  354.         {
  355.         }
  356.  
  357.     THugeVectorImp( const THugeVectorImp<T>& v ) :
  358.         TMHugeVectorImp<T,THugeStandardAllocator>( v )
  359.         {
  360.         }
  361.  
  362. };
  363.  
  364. template <class T> class THugeVectorIteratorImp :
  365.     public TMHugeVectorIteratorImp<T,THugeStandardAllocator>
  366. {
  367.  
  368. public:
  369.  
  370.     THugeVectorIteratorImp( const THugeVectorImp<T>& v ) :
  371.         TMHugeVectorIteratorImp<T,THugeStandardAllocator>(v)
  372.         {
  373.         }
  374.  
  375.     THugeVectorIteratorImp( const THugeVectorImp<T>& v,
  376.                         unsigned long start,
  377.                         unsigned long stop
  378.                         ) :
  379.         TMHugeVectorIteratorImp<T,THugeStandardAllocator>(v,start,stop)
  380.         {
  381.         }
  382.  
  383. };
  384.  
  385. /*------------------------------------------------------------------------*/
  386. /*                                                                        */
  387. /*  template <class T, class Alloc> class TMCHugeVectorImp                */
  388. /*  template <class T, class Alloc> class TMCHugeVectorIteratorImp        */
  389. /*                                                                        */
  390. /*  Implements a managed, counted vector of objects of type T.  Assumes   */
  391. /*  that T has meaningful copy semantics and a default constructor.       */
  392. /*                                                                        */
  393. /*------------------------------------------------------------------------*/
  394.  
  395. template <class T, class Alloc> class TMCHugeVectorImp :
  396.     public TMHugeVectorImp<T,Alloc>
  397. {
  398.  
  399. public:
  400.  
  401.     TMCHugeVectorImp() :
  402.         Count_(0),
  403.         Delta(0)
  404.         {
  405.         }
  406.  
  407.     TMCHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  408.         TMHugeVectorImp<T,Alloc>( sz ),
  409.         Count_(0),
  410.         Delta(d)
  411.         {
  412.         }
  413.  
  414.     int Add( const T& );
  415.     int AddAt( const T&, unsigned long);
  416.     int Detach( const T& t )
  417.         {
  418.         return Detach( Find(t) );
  419.         }
  420.  
  421.     int Detach( unsigned long loc );
  422.  
  423.     int IsEmpty() const
  424.         {
  425.         return Count_ == 0;
  426.         }
  427.  
  428.     void Flush( unsigned long stop = ULONG_MAX,
  429.                 unsigned long start = 0 )
  430.         {
  431.         TMHugeVectorImp<T,Alloc>::Flush( stop, start );
  432.         Count_ = 0;
  433.         }
  434.  
  435.     virtual unsigned long Find( const T& ) const;
  436.  
  437.     virtual unsigned long Top() const
  438.         {
  439.         return Count_;
  440.         }
  441.  
  442.     virtual unsigned long Count() const
  443.         {
  444.         return Count_;
  445.         }
  446.  
  447.     virtual unsigned long GetDelta() const
  448.         {
  449.         return Delta;
  450.         }
  451.  
  452. protected:
  453.  
  454.     unsigned long Count_;
  455.     unsigned long Delta;
  456.  
  457. };
  458.  
  459. template <class T,class Alloc> class TMCHugeVectorIteratorImp :
  460.     public TMHugeVectorIteratorImp<T,Alloc>
  461. {
  462.  
  463. public:
  464.  
  465.     TMCHugeVectorIteratorImp( const TMCHugeVectorImp<T,Alloc>& v ) :
  466.         TMHugeVectorIteratorImp<T,Alloc>(v)
  467.         {
  468.         }
  469.  
  470.     TMCHugeVectorIteratorImp( const TMCHugeVectorImp<T,Alloc>& v,
  471.                           unsigned long start,
  472.                           unsigned long stop
  473.                         ) :
  474.         TMHugeVectorIteratorImp<T,Alloc>(v,start,stop)
  475.         {
  476.         }
  477.  
  478. };
  479.  
  480. template <class T, class Alloc> int TMCHugeVectorImp<T,Alloc>::Add( const T& t )
  481. {
  482.     if( Count_ >= Lim && !Resize( Count_+1 ) )
  483.         return 0;
  484.     Data[Count_++] = t;
  485.     return 1;
  486. }
  487.  
  488. template <class T, class Alloc> 
  489. int TMCHugeVectorImp<T,Alloc>::AddAt( const T& t, unsigned long loc )
  490. {
  491.     if( loc >= Lim && !Resize(loc+1) )
  492.         return 0;
  493.     if( Count_ == Lim && !Resize(Lim+1) )
  494.         return 0;
  495.     if( loc > Count_ )
  496.         Count_ = loc;
  497.     for( unsigned long cur = Count_; cur > loc; cur-- )
  498.         Data[cur] = Data[cur-1];
  499.     Data[loc] = t;
  500.     Count_++;
  501.     return 1;
  502. }
  503.  
  504. template <class T, class Alloc>
  505. int TMCHugeVectorImp<T,Alloc>::Detach( unsigned long loc )
  506. {
  507.     if( loc >= Lim )
  508.         return 0;
  509.     if( loc >= Count_ )
  510.         {
  511.         Zero( loc, loc+1 ); // removing an element that's not
  512.         return 1;           // in the counted portion
  513.         }
  514.     Count_--;
  515.     for( unsigned long cur = loc; cur < Count_; cur++ )
  516.         Data[cur] = Data[cur+1];
  517.     return 1;
  518. }
  519.  
  520. template <class T, class Alloc>
  521. unsigned long TMCHugeVectorImp<T,Alloc>::Find( const T& t ) const
  522. {
  523.     for( unsigned long loc = 0; loc < Count_; loc++ )
  524.         if( Data[loc] == t )
  525.             return loc;
  526.     return ULONG_MAX;
  527. }
  528.  
  529. /*------------------------------------------------------------------------*/
  530. /*                                                                        */
  531. /*  template <class T> class TCHugeVectorImp                              */
  532. /*  template <class T> class TCHugeVectorIteratorImp                      */
  533. /*                                                                        */
  534. /*  Implements a counted vector of objects of type T using                */
  535. /*  THugeStandardAllocator as its memory manager.  Assumes                */
  536. /*  that T has meaningful copy semantics and a default constructor.       */
  537. /*                                                                        */
  538. /*------------------------------------------------------------------------*/
  539.  
  540. template <class T> class TCHugeVectorImp :
  541.     public TMCHugeVectorImp<T,THugeStandardAllocator>
  542. {
  543.  
  544. public:
  545.  
  546.     TCHugeVectorImp()
  547.         {
  548.         }
  549.  
  550.     TCHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  551.         TMCHugeVectorImp<T,THugeStandardAllocator>( sz, d )
  552.         {
  553.         }
  554.  
  555. };
  556.  
  557. template <class T> class TCHugeVectorIteratorImp :
  558.     public TMCHugeVectorIteratorImp<T,THugeStandardAllocator>
  559. {
  560.  
  561. public:
  562.  
  563.     TCHugeVectorIteratorImp( const TCHugeVectorImp<T>& v ) :
  564.         TMCHugeVectorIteratorImp<T,THugeStandardAllocator>(v)
  565.         {
  566.         }
  567.  
  568.     TCHugeVectorIteratorImp( const TCHugeVectorImp<T>& v,
  569.                          unsigned long start,
  570.                          unsigned long stop
  571.                         ) :
  572.         TMCHugeVectorIteratorImp<T,THugeStandardAllocator>(v,start,stop)
  573.         {
  574.         }
  575.  
  576. };
  577.  
  578. /*------------------------------------------------------------------------*/
  579. /*                                                                        */
  580. /*  template <class T, class Alloc> class TMSHugeVectorImp                */
  581. /*  template <class T, class Alloc> class TMSHugeVectorIteratorImp        */
  582. /*                                                                        */
  583. /*  Implements a managed, sorted vector of objects of type T.  Assumes    */
  584. /*  that T has meaningful copy semantics, a meaningful < operator,        */
  585. /*  and a default constructor.                                            */
  586. /*                                                                        */
  587. /*------------------------------------------------------------------------*/
  588.  
  589. template <class T, class Alloc> class TMSHugeVectorImp :
  590.     public TMCHugeVectorImp<T,Alloc>
  591. {
  592.  
  593. public:
  594.  
  595.     TMSHugeVectorImp()
  596.         {
  597.         }
  598.  
  599.     TMSHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  600.         TMCHugeVectorImp<T,Alloc>( sz, d )
  601.         {
  602.         }
  603.  
  604.     int Add( const T& );
  605.  
  606.     virtual unsigned long Find( const T& ) const;
  607.  
  608. };
  609.  
  610. template <class T,class Alloc> class TMSHugeVectorIteratorImp :
  611.     public TMCHugeVectorIteratorImp<T,Alloc>
  612. {
  613.  
  614. public:
  615.  
  616.     TMSHugeVectorIteratorImp( const TMSHugeVectorImp<T,Alloc>& v ) :
  617.         TMCHugeVectorIteratorImp<T,Alloc>(v)
  618.         {
  619.         }
  620.  
  621.     TMSHugeVectorIteratorImp( const TMSHugeVectorImp<T,Alloc>& v,
  622.                           unsigned long start,
  623.                           unsigned long stop
  624.                         ) :
  625.         TMCHugeVectorIteratorImp<T,Alloc>(v,start,stop)
  626.         {
  627.         }
  628.  
  629. };
  630.  
  631. template <class T, class Alloc> int TMSHugeVectorImp<T,Alloc>::Add( const T& t )
  632. {
  633.     unsigned long loc = Count_++;
  634.     if( Count_ > Lim )
  635.         if( !Resize( Count_ ) )
  636.             {
  637.             --Count_;
  638.             return 0;
  639.             }
  640.     while( loc > 0 && t < Data[loc-1] )
  641.         {
  642.         Data[loc] = Data[loc-1];
  643.         loc--;
  644.         }
  645.     Data[loc] = t;
  646.     return 1;
  647. }
  648.  
  649. template <class T, class Alloc>
  650. unsigned long TMSHugeVectorImp<T,Alloc>::Find( const T& t ) const
  651. {
  652.     if( Count_ == 0 )
  653.         return ULONG_MAX;
  654.  
  655.     unsigned long lower = 0;
  656.     unsigned long upper = Count_-1;
  657.  
  658.     while( lower < upper && upper != ULONG_MAX )
  659.         {
  660.         unsigned long middle = (lower+upper)/2;
  661.         if( (T __huge &)Data[middle] == (T&)t )
  662.             return middle;
  663.         if( (T __huge &)Data[middle] < (T&)t )
  664.             lower = middle+1;
  665.         else
  666.             upper = middle-1;
  667.         }
  668.  
  669.     if( lower == upper && (T __huge &)Data[lower] == (T&)t )
  670.         return lower;
  671.     else
  672.         return ULONG_MAX;
  673. }
  674.  
  675. /*------------------------------------------------------------------------*/
  676. /*                                                                        */
  677. /*  template <class T> class TSHugeVectorImp                              */
  678. /*  template <class T> class TSHugeVectorIteratorImp                      */
  679. /*                                                                        */
  680. /*  Implements a sorted vector of objects of type T using                 */
  681. /*  THugeStandardAllocator as its memory manager.  Assumes                */
  682. /*  that T has meaningful copy semantics, a meaningful < operator,        */
  683. /*  and a default constructor.                                            */
  684. /*                                                                        */
  685. /*------------------------------------------------------------------------*/
  686.  
  687. template <class T> class TSHugeVectorImp :
  688.     public TMSHugeVectorImp<T,THugeStandardAllocator>
  689. {
  690.  
  691. public:
  692.  
  693.     TSHugeVectorImp()
  694.         {
  695.         }
  696.  
  697.     TSHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  698.         TMSHugeVectorImp<T,THugeStandardAllocator>( sz, d )
  699.         {
  700.         }
  701.  
  702. };
  703.  
  704. template <class T> class TSHugeVectorIteratorImp :
  705.     public TMSHugeVectorIteratorImp<T,THugeStandardAllocator>
  706. {
  707.  
  708. public:
  709.  
  710.     TSHugeVectorIteratorImp( const TSHugeVectorImp<T>& v ) :
  711.         TMSHugeVectorIteratorImp<T,THugeStandardAllocator>(v)
  712.         {
  713.         }
  714.  
  715.     TSHugeVectorIteratorImp( const TSHugeVectorImp<T>& v,
  716.                          unsigned long start,
  717.                          unsigned long stop
  718.                         ) :
  719.         TMSHugeVectorIteratorImp<T,THugeStandardAllocator>(v,start,stop)
  720.         {
  721.         }
  722.  
  723. };
  724.  
  725. /*------------------------------------------------------------------------*/
  726. /*                                                                        */
  727. /*  template <class T,class Alloc> class TMIHugeVectorImp                 */
  728. /*                                                                        */
  729. /*  Implements a managed vector of pointers to objects of type T.         */
  730. /*  Since pointers always have meaningful copy semantics, this class      */
  731. /*  can handle any type of object.                                        */
  732. /*                                                                        */
  733. /*------------------------------------------------------------------------*/
  734.  
  735. template <class T,class Alloc> class TMIHugeVectorImp :
  736.     public THugeVectorImpBase<TVoidPointer,Alloc>
  737. {
  738.  
  739. public:
  740.  
  741.     typedef void (*IterFunc)(T&, void *);
  742.     typedef int  (*CondFunc)(const T&, void *);
  743.  
  744.     TMIHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  745.         THugeVectorImpBase<TVoidPointer,Alloc>(sz,d) {}
  746.  
  747.     T * __huge & operator [] ( unsigned long index )
  748.         {
  749.         PRECONDITION( Lim == 0 || Data != 0 && index < Lim );
  750.         return *STATIC_CAST(T * __huge *,STATIC_CAST(void __huge *,&Data[index]));
  751.         }
  752.  
  753.     T * __huge & operator [] ( unsigned long index ) const
  754.         {
  755.         PRECONDITION( Lim > 0 && Data != 0 && index < Lim );
  756.         return *STATIC_CAST(T * __huge *,STATIC_CAST(void __huge *,&Data[index]));
  757.         }
  758.  
  759.     void Flush( unsigned del = 0,
  760.                 unsigned long stop = ULONG_MAX,
  761.                 unsigned long start = 0 );
  762.  
  763.     void ForEach( IterFunc iter, void *args )
  764.         {
  765.         ForEach( iter, args, 0, Count() );
  766.         }
  767.  
  768.     void ForEach( IterFunc iter, void *args,
  769.                   unsigned long start, unsigned long stop );
  770.  
  771.     T *FirstThat( CondFunc cond, void *args ) const
  772.         {
  773.         return FirstThat( cond, args, 0, Count() );
  774.         }
  775.  
  776.     T *FirstThat( CondFunc cond, void *args,
  777.                            unsigned long start, unsigned long stop ) const;
  778.  
  779.     T *LastThat( CondFunc cond, void *args ) const
  780.         {
  781.         return LastThat( cond, args, 0, Count() );
  782.         }
  783.  
  784.     T *LastThat( CondFunc cond, void *args,
  785.                           unsigned long start, unsigned long stop ) const;
  786.  
  787. protected:
  788.  
  789.     void Zero( unsigned long, unsigned long);
  790.  
  791. private:
  792.  
  793.     static void DelObj(T &, void * );
  794.  
  795. };
  796.  
  797. template <class T, class Alloc>
  798. void TMIHugeVectorImp<T,Alloc>::DelObj(T & tRef, void * )
  799. {
  800.     delete &tRef ;
  801. }
  802.  
  803. template <class T, class Alloc>
  804. void TMIHugeVectorImp<T,Alloc>::Flush( unsigned del,
  805.                                    unsigned long upr,
  806.                                    unsigned long lwr )
  807. {
  808.     upr = min( upr, Limit() );
  809.     if( del )
  810.         ForEach( DelObj, 0, lwr, upr );
  811.     Zero( lwr, upr );
  812. }
  813.  
  814. template <class T, class Alloc>
  815. void TMIHugeVectorImp<T,Alloc>::ForEach( IterFunc iter, void *args,
  816.                                     unsigned long start, unsigned long stop )
  817. {
  818.     for( unsigned long cur = start; cur < stop; cur++ )
  819.         if( Data[cur] != 0 )
  820.             iter( *STATIC_CAST(T *,STATIC_CAST(void *,Data[cur])), args );
  821. }
  822.  
  823. template <class T, class Alloc>
  824. T *TMIHugeVectorImp<T,Alloc>::FirstThat( CondFunc cond,
  825.                                      void *args,
  826.                                      unsigned long start,
  827.                                      unsigned long stop ) const
  828. {
  829.     for( unsigned long cur = start; cur < stop; cur++ )
  830.         if( Data[cur] != 0 &&
  831.             cond( *STATIC_CAST(T *,STATIC_CAST(void *,Data[cur])), args ) != 0 )
  832.             return STATIC_CAST(T *,STATIC_CAST(void *,Data[cur]));
  833.     return 0;
  834. }
  835.  
  836. template <class T, class Alloc>
  837. T *TMIHugeVectorImp<T,Alloc>::LastThat( CondFunc cond,
  838.                                     void *args,
  839.                                     unsigned long start,
  840.                                     unsigned long stop ) const
  841. {
  842.     T *res = 0;
  843.     for( unsigned long cur = start; cur < stop; cur++ )
  844.         if( Data[cur] != 0 &&
  845.             cond( *STATIC_CAST(T *,STATIC_CAST(void *,Data[cur])), args ) != 0 )
  846.             res = STATIC_CAST(T *,STATIC_CAST(void *,Data[cur]));
  847.     return res;
  848. }
  849.  
  850. template <class T, class Alloc>
  851. void TMIHugeVectorImp<T,Alloc>::Zero( unsigned long lwr, unsigned long upr )
  852. {
  853.     for( unsigned long i = lwr; i < min( Limit(), upr ); i++ )
  854.         Data[i] = 0;
  855. }
  856.  
  857. /*------------------------------------------------------------------------*/
  858. /*                                                                        */
  859. /*  template <class T,class Alloc> class TMIHugeVectorIteratorImp         */
  860. /*                                                                        */
  861. /*  Implements an iterator for a managed indirect vector of pointers to   */
  862. /*  objects of type T.                                                    */
  863. /*                                                                        */
  864. /*------------------------------------------------------------------------*/
  865.  
  866. template <class T, class Alloc> class TMIHugeVectorIteratorImp
  867. {
  868.  
  869. public:
  870.  
  871.     TMIHugeVectorIteratorImp( const TMIHugeVectorImp<T,Alloc>& v )
  872.         {
  873.         Vect = &v;
  874.         Restart(0,v.Top());
  875.         }
  876.  
  877.     TMIHugeVectorIteratorImp( const TMIHugeVectorImp<T,Alloc>& v,
  878.                           unsigned long start,
  879.                           unsigned long stop )
  880.         {
  881.         Vect = &v;
  882.         Restart( start, stop );
  883.         }
  884.  
  885.     operator int() const
  886.         {
  887.         return Cur < Upper;
  888.         }
  889.  
  890.     T *Current() const
  891.         {
  892.         PRECONDITION( Cur < Upper );
  893.         return STATIC_CAST(T *,STATIC_CAST(void *,(*Vect)[Cur]));
  894.         }
  895.  
  896.     T *operator ++ ( int )
  897.         {
  898.         T *temp = Current();
  899.         Cur++;
  900.         return temp;
  901.         }
  902.  
  903.     T *operator ++ ()
  904.         {
  905.         PRECONDITION( Cur < Upper );
  906.         Cur++;
  907.         return Current();
  908.         }
  909.  
  910.     void Restart()
  911.         {
  912.         Restart(Lower,Upper);
  913.         }
  914.  
  915.     void Restart( unsigned long start, unsigned long stop )
  916.         {
  917.         Cur = Lower = start;
  918.         Upper = stop;
  919.         }
  920.  
  921. private:
  922.  
  923.     const TMIHugeVectorImp<T,Alloc> *Vect;
  924.     unsigned long Cur;
  925.     unsigned long Lower, Upper;
  926.  
  927. };
  928.  
  929. /*------------------------------------------------------------------------*/
  930. /*                                                                        */
  931. /*  template <class T> class TIHugeVectorImp                              */
  932. /*  template <class T> class TIHugeVectorIteratorImp                      */
  933. /*                                                                        */
  934. /*  Implements a vector of pointers to objects of type T using            */
  935. /*  THugeStandardAllocator as its memory manager.                         */
  936. /*  Since pointers always have meaningful copy semantics, this class      */
  937. /*  can handle any type of object.                                        */
  938. /*                                                                        */
  939. /*------------------------------------------------------------------------*/
  940.  
  941. template <class T> class TIHugeVectorImp :
  942.     public TMIHugeVectorImp<T,THugeStandardAllocator>
  943. {
  944.  
  945. public:
  946.  
  947.     TIHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  948.         TMIHugeVectorImp<T,THugeStandardAllocator>(sz,d)
  949.         {
  950.         }
  951.  
  952. };
  953.  
  954. template <class T> class TIHugeVectorIteratorImp :
  955.     public TMIHugeVectorIteratorImp<T,THugeStandardAllocator>
  956. {
  957.  
  958. public:
  959.  
  960.     TIHugeVectorIteratorImp( const TIHugeVectorImp<T>& v ) :
  961.         TMIHugeVectorIteratorImp<T,THugeStandardAllocator>(v)
  962.         {
  963.         }
  964.  
  965.     TIHugeVectorIteratorImp( const TIHugeVectorImp<T>& v,
  966.                          unsigned long l, unsigned long u ) :
  967.         TMIHugeVectorIteratorImp<T,THugeStandardAllocator>(v,l,u)
  968.         {
  969.         }
  970.  
  971. };
  972.  
  973. /*------------------------------------------------------------------------*/
  974. /*                                                                        */
  975. /*  template <class T,class Alloc> class TMICHugeVectorImp                */
  976. /*  template <class T,class Alloc> class TMICHugeVectorIteratorImp        */
  977. /*                                                                        */
  978. /*  Implements a managed, counted vector of pointers to objects of type T.*/
  979. /*  Since pointers always have meaningful copy semantics, this class      */
  980. /*  can handle any type of object.                                        */
  981. /*                                                                        */
  982. /*------------------------------------------------------------------------*/
  983.  
  984. template <class T,class Alloc> class TMICHugeVectorImp :
  985.     public TMIHugeVectorImp<T,Alloc>
  986. {
  987.  
  988. public:
  989.  
  990.     TMICHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  991.         TMIHugeVectorImp<T,Alloc>(sz), Delta(d), Count_(0) {}
  992.  
  993.     int Add( T *t );
  994.     int AddAt( T *, unsigned long);
  995.     int Detach( const T *t, int del = 0 )
  996.         {
  997.         return Detach( Find(t), del );
  998.         }
  999.  
  1000.     int Detach( unsigned long loc, int del = 0 );
  1001.  
  1002.     int IsEmpty() const
  1003.         {
  1004.         return Count_ == 0;
  1005.         }
  1006.  
  1007.     void Flush( int del = 0,
  1008.                 unsigned long stop = ULONG_MAX,
  1009.                 unsigned long start = 0 )
  1010.         {
  1011.         TMIHugeVectorImp<T,Alloc>::Flush( del, stop, start );
  1012.         Count_ = 0;
  1013.         }
  1014.  
  1015.     unsigned long Find( const T *t ) const;
  1016.  
  1017.     virtual unsigned long Top() const
  1018.         {
  1019.         return Count_;
  1020.         }
  1021.  
  1022.     virtual unsigned long Count() const
  1023.         {
  1024.         return Count_;
  1025.         }
  1026.  
  1027.     virtual unsigned long GetDelta() const
  1028.         {
  1029.         return Delta;
  1030.         }
  1031.  
  1032. protected:
  1033.  
  1034.     unsigned long Count_;
  1035.     unsigned long Delta;
  1036.  
  1037. };
  1038.  
  1039. template <class T,class Alloc> class TMICHugeVectorIteratorImp :
  1040.     public TMIHugeVectorIteratorImp<T,Alloc>
  1041. {
  1042.  
  1043. public:
  1044.  
  1045.     TMICHugeVectorIteratorImp( const TMICHugeVectorImp<T,Alloc>& v ) :
  1046.         TMIHugeVectorIteratorImp<T,Alloc>(v)
  1047.         {
  1048.         }
  1049.  
  1050.     TMICHugeVectorIteratorImp( const TMICHugeVectorImp<T,Alloc>& v,
  1051.                            unsigned long start,
  1052.                            unsigned long stop ) :
  1053.         TMIHugeVectorIteratorImp<T,Alloc>(v,start,stop)
  1054.         {
  1055.         }
  1056.  
  1057. };
  1058.  
  1059. template <class T, class Alloc> 
  1060. int TMICHugeVectorImp<T,Alloc>::AddAt( T *t, unsigned long loc )
  1061. {
  1062.     if( loc >= Lim && !Resize(loc+1) )
  1063.         return 0;
  1064.     if( Count_ == Lim && !Resize(Lim+1) )
  1065.         return 0;
  1066.     if( loc > Count_ )
  1067.         Count_ = loc;
  1068.     for( unsigned long cur = Count_; cur > loc; cur-- )
  1069.         Data[cur] = Data[cur-1];
  1070.     Data[loc] = t;
  1071.     Count_++;
  1072.     return 1;
  1073. }
  1074.  
  1075. template <class T, class Alloc>
  1076. int TMICHugeVectorImp<T,Alloc>::Detach( unsigned long loc, int del )
  1077. {
  1078.     if( loc >= Lim )
  1079.         return 0;
  1080.     if( del )
  1081.         delete STATIC_CAST(T *,STATIC_CAST(void *,Data[loc]));
  1082.     if( loc >= Count_ )
  1083.         {
  1084.         Zero( loc, loc+1 ); // removing an element that's not
  1085.         return 1;           // in the counted portion
  1086.         }
  1087.     Count_--;
  1088.     for( unsigned long cur = loc; cur < Count_; cur++ )
  1089.         Data[cur] = Data[cur+1];
  1090.     Zero( Count_, Count_+1 );
  1091.     return 1;
  1092. }
  1093.  
  1094. template <class T,class Alloc>
  1095. unsigned long TMICHugeVectorImp<T,Alloc>::Find( const T *t ) const
  1096. {
  1097.     if( Top() != 0 )
  1098.         {
  1099.         for( unsigned long loc = 0; loc < Top(); loc++ )
  1100.             if( Data[loc] &&
  1101.               *STATIC_CAST(T *,STATIC_CAST(void *,Data[loc])) == *t )
  1102.                 return loc;
  1103.         }
  1104.     return ULONG_MAX;
  1105. }
  1106.  
  1107. template <class T,class Alloc> int TMICHugeVectorImp<T,Alloc>::Add( T *t )
  1108. {
  1109.     while( Count_ < Limit() && (*this)[Count_] != 0 )
  1110.         Count_++;
  1111.     if( Count_ >= Lim && !Resize( Count_+1 ) )
  1112.         return 0;
  1113.     Data[Count_++] = t;
  1114.     return 1;
  1115. }
  1116.  
  1117. /*------------------------------------------------------------------------*/
  1118. /*                                                                        */
  1119. /*  template <class T> class TICHugeVectorImp                             */
  1120. /*  template <class T> class TICHugeVectorIteratorImp                     */
  1121. /*                                                                        */
  1122. /*  Implements a counted vector of pointers to objects of type T using    */
  1123. /*  THugeStandardAllocator as its memory manager.                         */
  1124. /*  Since pointers always have meaningful copy semantics, this class      */
  1125. /*  can handle any type of object.                                        */
  1126. /*                                                                        */
  1127. /*------------------------------------------------------------------------*/
  1128.  
  1129. template <class T> class TICHugeVectorImp :
  1130.     public TMICHugeVectorImp<T,THugeStandardAllocator>
  1131. {
  1132.  
  1133. public:
  1134.  
  1135.     TICHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  1136.         TMICHugeVectorImp<T,THugeStandardAllocator>( sz, d )
  1137.         {
  1138.         }
  1139.  
  1140. };
  1141.  
  1142. template <class T> class TICHugeVectorIteratorImp :
  1143.     public TMICHugeVectorIteratorImp<T,THugeStandardAllocator>
  1144. {
  1145.  
  1146. public:
  1147.  
  1148.     TICHugeVectorIteratorImp( const TICHugeVectorImp<T>& v ) :
  1149.         TMICHugeVectorIteratorImp<T,THugeStandardAllocator>(v)
  1150.         {
  1151.         }
  1152.  
  1153.     TICHugeVectorIteratorImp( const TICHugeVectorImp<T>& v,
  1154.                           unsigned long l, unsigned long u ) :
  1155.         TMICHugeVectorIteratorImp<T,THugeStandardAllocator>(v,l,u)
  1156.         {
  1157.         }
  1158.  
  1159. };
  1160.  
  1161. /*------------------------------------------------------------------------*/
  1162. /*                                                                        */
  1163. /*  template <class T,class Alloc> class TMISHugeVectorImp                */
  1164. /*  template <class T,class Alloc> class TMISHugeVectorIteratorImp        */
  1165. /*                                                                        */
  1166. /*  Implements a managed, sorted vector of pointers to objects of type T. */
  1167. /*  This is implemented through the template TInternalIHugeVectorImp.     */
  1168. /*  Since pointers always have meaningful copy semantics, this class      */
  1169. /*  can handle any type of object.                                        */
  1170. /*                                                                        */
  1171. /*------------------------------------------------------------------------*/
  1172.  
  1173. template <class T,class Alloc> class TMISHugeVectorImp :
  1174.     public TMICHugeVectorImp<T,Alloc>
  1175. {
  1176.  
  1177. public:
  1178.  
  1179.     TMISHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  1180.         TMICHugeVectorImp<T,Alloc>(sz)
  1181.         {
  1182.         Delta = d;
  1183.         }
  1184.  
  1185.     unsigned long Find( const T *t ) const;
  1186.     int Add( T *t );
  1187.  
  1188. };
  1189.  
  1190. template <class T,class Alloc> class TMISHugeVectorIteratorImp :
  1191.     public TMICHugeVectorIteratorImp<T,Alloc>
  1192. {
  1193.  
  1194. public:
  1195.  
  1196.     TMISHugeVectorIteratorImp( const TMISHugeVectorImp<T,Alloc>& v ) :
  1197.         TMICHugeVectorIteratorImp<T,Alloc>(v)
  1198.         {
  1199.         }
  1200.  
  1201.     TMISHugeVectorIteratorImp( const TMISHugeVectorImp<T,Alloc>& v,
  1202.                            unsigned long start,
  1203.                            unsigned long stop ) :
  1204.         TMICHugeVectorIteratorImp<T,Alloc>(v,start,stop)
  1205.         {
  1206.         }
  1207.  
  1208. };
  1209.  
  1210. template <class T,class Alloc>
  1211. unsigned long TMISHugeVectorImp<T,Alloc>::Find( const T *t ) const
  1212. {
  1213.     if( Count_ == 0 )
  1214.         return ULONG_MAX;
  1215.  
  1216.     unsigned long lower = 0;
  1217.     unsigned long upper = Count_-1;
  1218.  
  1219.     while( lower < upper && upper != ULONG_MAX )
  1220.         {
  1221.         unsigned long middle = (lower+upper)/2;
  1222.         if( *STATIC_CAST(T *,STATIC_CAST(void *,Data[middle])) == *t )
  1223.             return middle;
  1224.         if( *STATIC_CAST(T *,STATIC_CAST(void *,Data[middle])) < *t )
  1225.             lower = middle+1;
  1226.         else
  1227.             upper = middle-1;
  1228.         }
  1229.  
  1230.     if( lower == upper &&
  1231.         *STATIC_CAST(T *,STATIC_CAST(void *,Data[lower])) == *t )
  1232.         return lower;
  1233.     else
  1234.         return ULONG_MAX;
  1235. }
  1236.  
  1237. template <class T,class Alloc> int TMISHugeVectorImp<T,Alloc>::Add( T *t )
  1238. {
  1239.     unsigned long loc = Count_++;
  1240.     if( Count_ > Lim )
  1241.         if( !Resize( Count_ ) )
  1242.             {
  1243.             --Count_;
  1244.             return 0;
  1245.             }
  1246.     while( loc > 0 &&
  1247.            *t < *STATIC_CAST(T *,STATIC_CAST(void *,(*this)[loc-1])) )
  1248.         {
  1249.         Data[loc] = Data[loc-1];
  1250.         loc--;
  1251.         }
  1252.     Data[loc] = t;
  1253.     return 1;
  1254. }
  1255.  
  1256. /*------------------------------------------------------------------------*/
  1257. /*                                                                        */
  1258. /*  template <class T> class TISHugeVectorImp                             */
  1259. /*  template <class T> class TISHugeVectorIteratorImp                     */
  1260. /*                                                                        */
  1261. /*  Implements a sorted vector of pointers to objects of type T using     */
  1262. /*  THugeStandardAllocator as its memory manager.                         */
  1263. /*  This is implemented through the template TInternalIHugeVectorImp.     */
  1264. /*  Since pointers always have meaningful copy semantics, this class      */
  1265. /*  can handle any type of object.                                        */
  1266. /*                                                                        */
  1267. /*------------------------------------------------------------------------*/
  1268.  
  1269. template <class T> class TISHugeVectorImp :
  1270.     public TMISHugeVectorImp<T,THugeStandardAllocator>
  1271. {
  1272.  
  1273. public:
  1274.  
  1275.     TISHugeVectorImp( unsigned long sz, unsigned long d = 0 ) :
  1276.         TMISHugeVectorImp<T,THugeStandardAllocator>( sz, d )
  1277.         {
  1278.         }
  1279.  
  1280. };
  1281.  
  1282. template <class T> class TISHugeVectorIteratorImp :
  1283.     public TMISHugeVectorIteratorImp<T,THugeStandardAllocator>
  1284. {
  1285.  
  1286. public:
  1287.  
  1288.     TISHugeVectorIteratorImp( const TISHugeVectorImp<T>& v ) :
  1289.         TMISHugeVectorIteratorImp<T,THugeStandardAllocator>(v)
  1290.         {
  1291.         }
  1292.  
  1293.     TISHugeVectorIteratorImp( const TISHugeVectorImp<T>& v,
  1294.                           unsigned long l, unsigned long u
  1295.                          ) :
  1296.         TMISHugeVectorIteratorImp<T,THugeStandardAllocator>(v,l,u)
  1297.         {
  1298.         }
  1299.  
  1300. };
  1301.  
  1302. #if defined( BI_CLASSLIB_NO_po )
  1303. #pragma option -po.
  1304. #endif
  1305.  
  1306. #pragma option -Vo.
  1307.  
  1308. #endif  // HVECTIMP_H
  1309.